//https://leetcode.cn/problems/daily-temperatures/
package codeRandomThoughts.Test739每日温度;

import java.util.Stack;

//单调栈
//用栈实现
public class Solution {
    public int[] dailyTemperatures(int[] temperatures) {
        //单调栈
        //我们这里要从左往右遍历
        //要保存栈顶到栈底是单调递增的
        //如果发现元素放入会导致不单调
        //弹出栈顶元素,每个元素在弹出的时候计算自己和比自己大的元素的距离
        //如果元素没有弹出,说明没有比他大的元素,距离自然为0
        Stack<Integer> monotonicStack = new Stack<>();
        int[] result = new int[temperatures.length];

        //遍历温度
        for (int i = 0; i < temperatures.length; i++) {
            while (!monotonicStack.isEmpty() && temperatures[i] > temperatures[monotonicStack.peek()]) {
                //元素弹出的时候计算距离
                Integer pop = monotonicStack.pop();
                result[pop] = i - pop;
            }

            //此时放入元素满足单调栈的规则
            monotonicStack.push(i);
        }

        return result;
    }
}
